#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include "heap.h"
#include "basic.h"
#define LEN     60
#define EDGE_NUM (rst->gx)*(rst->gy - 1) + (rst->gy)*(rst->gx - 1)
#define INFTY   2147483647
//      
//      some basic functions in graph
//
point   id_to_pt ( int id, routingInst *rst )
{
        point   p;
        p.x = id % (rst->gx);
        p.y = id / (rst->gx);
        return  p;
}
int     pos_to_id ( int x, int y, routingInst *rst )
{
        return y*(rst->gx)+x;
}
int     pt_to_id ( point pt, routingInst *rst )
{
        return  pt.y*(rst->gx)+pt.x;
}
int     find_edge_id (int x1, int y1, int x2, int y2, routingInst *rst )
{
        int     x,y;
        if ( y1 == y2 )
        {
                y = y1;
                x = min (x1, x2);
                return  ((rst->gx)-1)*y + x;
        }
        if ( x1 == x2 ) 
        {
                x = x1;
                y = min ( y1, y2 );
                return  ((rst->gx)-1)*(rst->gy)+(rst->gx)*y + x;
        }
        return -1;
}
int     pt_dist ( int id1, int id2, routingInst *rst )
{
        point   p1 = id_to_pt ( id1, rst );
        point   p2 = id_to_pt ( id2, rst );
        return  abs(p1.x - p2.x)+abs(p1.y - p2.y);
}
int     is_flat ( int id1, int id2, routingInst *rst )
{
        point   p1 = id_to_pt ( id1, rst );
        point   p2 = id_to_pt ( id2, rst );
        return (p1.x==p2.x)||(p1.y==p2.y);
}
int     is_in_line ( int id1, int id2, int id3, routingInst *rst )
{
        int     gx = rst->gx;
        if ( (id1/gx==id2/gx) && (id2/gx==id3/gx ) )
                return  1;
        if ( (id1%gx==id2%gx) && (id2%gx==id3%gx ) )
                return  1;
        return  0; 
}
//      
//      related functions
//
void    ld_edgeUtils ( int net_id, routingInst *rst )
{
        net     *n = rst->nets + net_id;
        for ( int_LL *node = n->edges; node->next; node = node->next )
                ++ rst->edgeUtils[node->next->num];
}
float   dfn_weight ( int util, int cap, float hist )
{ 
        if ( cap )
                return  (10.0*util)/cap;
        else
                return  100;
}
void    ld_hist ( routingInst *rst )
{
        for ( int i = 0; i<rst->numEdges; i++ )
                if ( rst->edgeUtils[i] > rst->edgeCaps[i] )
                        rst->hist[i] = rst->hist[i] + 1;
}
void    ld_edgeWeights ( routingInst *rst )
{
        for ( int i = 0; i<rst->numEdges; i++ )
                rst->edgeWeights[i] = dfn_weight ( rst->edgeUtils[i], rst->edgeCaps[i], rst->hist[i] );
}
void    ld_netWeights ( int net_id, routingInst *rst )
{ float   tot = 0;
        net     *n = rst->nets + net_id;
        for ( int_LL *node = n->edges; node->next; node = node->next )
//                tot += rst->edgeWeights[node->next->num];
                tot ++;
        rst->netWeights[net_id] = tot;
}
int     ofl     ( routingInst *rst )
{
        int     ofl=0;
        for (int i=0; i<rst->numEdges; i++)
                if ( rst->edgeUtils[i] > rst->edgeCaps[i] )
                {
                        ofl += (rst->edgeUtils[i] - rst->edgeCaps[i]);
                }
        return  ofl;
}
void    refresh ( routingInst *rst )
{
        int     numNets = rst->numNets;
        ld_hist ( rst );
        for ( int i = 0; i<numNets; i++ )
                ld_netWeights ( i, rst );
        ld_edgeWeights (rst);
}
int     seg_contain_edge ( segment *seg, int edge_id, routingInst *rst )
{
        for ( int i = 0; i < pt_dist(seg->s, seg->t, rst); i++ )
                if ( seg->edges[i] == edge_id )
                        return 1;
        return 0;
}
segment simple_connect ( int s, int t, routingInst *rst )
{
        segment         seg;
        seg.s = s;
        seg.t = t;
        seg.dist = pt_dist(s,t,rst);
        seg.edges = new_array ( seg.dist );
        point   p1 = id_to_pt ( s, rst );
        point   p2 = id_to_pt ( t, rst );

        int     k = 0;
        if ( p1.y == p2.y )
        {
                for ( int x = min(p1.x, p2.x); x < max(p1.x, p2.x); x++)
                {
                        int     edge_id = find_edge_id (x,p1.y,x+1,p2.y,rst);
                        seg.edges[k++] = edge_id;
                }
                return seg;
        }
        if ( p1.x == p2.x )
        {
                for ( int y = min(p1.y, p2.y); y < max(p1.y, p2.y); y++)
                {
                        int     edge_id = find_edge_id (p1.x,y,p2.x,y+1,rst);
                        seg.edges[k++] = edge_id;
                }
                return seg;
        }
        return  seg;
}
int     route_contain_edge ( route *r, int edge_id, routingInst *rst )
{
        if (!r->state)
                return 0;
        else
        {
                for ( int i = 0; i < r->numSegs; i++ )
                        if ( seg_contain_edge ( r->seg+i, edge_id, rst ) )
                                return 1;
                return 0;
        }
}
int     net_contain_edge ( int net_id, int edge_id, routingInst *rst )
{
        net     *n = rst->nets+net_id;
        return  find_int_LL ( edge_id, n->edges );
}
int     net_contain_node ( int v, int net_id, routingInst *rst )
{
        point   p = id_to_pt ( v, rst );
        int     x = p.x;
        int     y = p.y;
        if ( p.x > 0  && net_contain_edge ( net_id, find_edge_id (x-1,y,x,y,rst), rst) )          
                return  1;
        if ( p.x <rst->gx-1  && net_contain_edge ( net_id, find_edge_id (x+1,y,x,y,rst), rst) )          
                return  1;
        if ( p.y > 0  && net_contain_edge ( net_id, find_edge_id (x,y-1,x,y,rst), rst) )          
                return  1;
        if ( p.y <rst->gy-1  && net_contain_edge ( net_id, find_edge_id (x,y+1,x,y,rst), rst) )          
                return  1;
        return  0;
}
int     check_cyclic ( int net_id, routingInst *rst )
{
        net     *n = rst->nets + net_id;
        int     *visited = new_array ( rst->gx * rst->gy );
        int_LL  *queue = new_int_LL ();
        insert_int_LL ( n->pins[0], queue );
        visited[n->pins[0]] = 1;
        while ( !queue->next )
        {
                int     tmp = deQ_int_LL (queue); 
                int     x = tmp%rst->gx;
                int     y = tmp/rst->gx;
                if ( x > 0 && net_contain_node ( y*rst->gx+x-1, net_id, rst ) )
                {
                        int     adj = y*rst->gx+x-1;
                        if ( visited[adj] )
                        {
                                free(visited);
                                return  1;
                        }
                        else
                        {
                                visited[adj] = 1;
                                insert_int_LL ( adj, queue );
                        }
                }
                if ( y > 0 && net_contain_node ( (y-1)*rst->gx+x, net_id, rst ) )
                {
                        int     adj = (y-1)*rst->gx+x;
                        if ( visited[adj] )
                        {
                                free(visited);
                                return  1;
                        }
                        else
                        {
                                visited[adj] = 1;
                                insert_int_LL ( adj, queue );
                        }
                }
                if ( x < rst->gx-1 && net_contain_node ( y*rst->gx+x+1, net_id, rst ) )
                {
                        int     adj = y*rst->gx+x+1;
                        if ( visited[adj] )
                        {
                                free(visited);
                                return  1;
                        }
                        else
                        {
                                visited[adj] = 1;
                                insert_int_LL ( adj, queue );
                        }
                }
                if ( y < rst->gy-1 && net_contain_node ( (y+1)*rst->gx+x, net_id, rst ) )
                {
                        int     adj = (y+1)*rst->gx+x;
                        if ( visited[adj] )
                        {
                                free(visited);
                                return  1;
                        }
                        else
                        {
                                visited[adj] = 1;
                                insert_int_LL ( adj, queue );
                        }
                }
        }
        free ( visited );
        return 0;
}

int     est_segment ( segment *seg, int net_id, routingInst *rst )
{
        int     est_ofl = 0;
        for ( int i = 0; i < seg->dist; i++ )
        {
                int     edge_id = seg->edges[i];
                if ( !net_contain_edge ( net_id, edge_id, rst ) && (rst->edgeUtils[edge_id]>=rst->edgeCaps[edge_id]) )
                        ++ est_ofl;
        }
        return  est_ofl;
}

void    ld_seg_net ( segment *s, int net_id, routingInst* rst )
{
        for (int i = 0; i<s->dist; i++ )
                insert_int_LL (s->edges[i], rst->nets[net_id].edges );
}

void    rip_up ( int net_id, routingInst *rst )
{
        net     *n = rst->nets + net_id;
        for ( int_LL *node = n->edges; node->next; node=node->next )
        {
                int     id = node->next->num;
                -- rst->edgeUtils[id];
                rst->edgeWeights[id] = dfn_weight( rst->edgeUtils[id], rst->edgeCaps[id], rst->hist[id] );
        }
        for ( int i = 0; i < n->numPins-1; i++ )
                n->r[i].state = 0;
        n->edges->next = NULL;
        rst->netWeights[net_id] = 0; 
}
void    pin_ordering ( int net_id, routingInst *rst )
{
        /* to find shortest path passing all nodes in net */
        net     *n = rst->nets + net_id;
        int     NUM = rst->nets[net_id].numPins;
        int     *pins = rst->nets[net_id].pins;
        int     *state = new_array ( NUM );        // 0:out 1:in
        assign_array ( state, NUM, 0 );
        int     dist = INFTY;

        int     pt1 = 0;
        int     pt2 = 0;
        for ( int i = 0; i<NUM; i++ )
                for ( int j =0; j<NUM; j++ )
                        if ( (i!=j) && pt_dist ( pins[i], pins[j], rst ) < dist )
                        {
                                dist = pt_dist(pins[i],pins[j], rst);
                                pt1 = i;        pt2 = j;
                        }
        state[pt1] = 1; state[pt2] = 1;
        n->r[0].s = pins[pt1];
        n->r[0].t = pins[pt2];
        n->r[0].state = 0;
        int     k = 1;
        while ( k < NUM-1 )
        {
                int     dist = INFTY;
                for ( int i = 0; i<NUM; i++ )
                        for ( int j = 0; j<NUM; j++ )
                                if ( state[i] && !state[j] && pt_dist(pins[i],pins[j],rst)<dist )
                                {
                                        dist = pt_dist ( pins[i], pins[j], rst );
                                        pt1 = i;        pt2 = j;
                                }
                state[pt2] = 1;
                n->r[k].s = pins[pt1];
                n->r[k].t = pins[pt2];
                n->r[k].state = 0;
                k ++;
        }

}
int     *net_ordering_size ( routingInst *rst )
{
        float   *score = new_float_array ( rst->numNets );
        for ( int i = 0; i<rst->numNets; i++ )
                score[i] = (float)rst->nets[i].numPins;
        int     *sort = sort_array ( score, rst->numNets );
        reverse_array ( sort, rst->numNets );
        return  sort;
}

void    print_single_route ( FILE *fp, route *r, routingInst *rst )
{
        int     gx = rst->gx;
        if ( r->state )
        {
                for ( int i = 0; i < r->numSegs; i++ )
                {
                        int     s = r->seg[i].s;
                        int     t = r->seg[i].t;
                        fprintf ( fp, "(%d,%d)-(%d,%d)\n", s%gx, s/gx, t%gx, t/gx );
                }
        }
}
void    print_single_net ( FILE *fp, int net_id, routingInst *rst )
{
        net     *n = rst->nets + net_id;
        fprintf ( fp, "n%d\n", net_id );
        for ( int i = 0; i< n->numPins-1; i++ )
                print_single_route ( fp, n->r+i, rst );
        fprintf ( fp, "!\n" );
}
void    ptr_rst ( FILE *fp, routingInst *rst )
{
        for ( int i = 0; i<rst->numNets; i++ )
                print_single_net ( fp, i, rst );
}

void    L_corner ( int *L, int s, int t, int net_id, routingInst *rst )
{
        int     p1 = rst->gx * (s/rst->gx) + t%rst->gx;
        int     p2 = rst->gx * (t/rst->gx) + s%rst->gx;
        segment s11 = simple_connect ( s, p1, rst );
        segment s12 = simple_connect ( t, p1, rst );
        segment s21 = simple_connect ( s, p2, rst );
        segment s22 = simple_connect ( t, p2, rst );
        if ( est_segment(&s11, net_id, rst )+est_segment(&s12,net_id,rst) <= est_segment(&s21,net_id,rst)+est_segment(&s22,net_id,rst) )
        {
                L[0] = est_segment(&s11,net_id,rst)+est_segment(&s12,net_id,rst);
                L[1] = p1;
        }
        else
        {
                L[0] = est_segment(&s21,net_id,rst)+est_segment(&s22,net_id,rst);
                L[1] = p2;
        }
}
void    simple_route ( route *r, int net_id, routingInst *rst )
{
        int     s = r->s;
        int     t = r->t;
        r->state = 1;
        if (is_flat (s,t,rst) )
        {
                r->numSegs = 1;
                r->seg = (segment*)malloc(sizeof(segment));
                r->seg[0] = simple_connect ( s,t,rst );
                ld_seg_net ( r->seg, net_id, rst );
        }
        else
        {
                int     L[2];
                L_corner (L,s,t,net_id,rst);
                int     p = L[1];
                segment s1 = simple_connect ( s, p, rst );
                segment s2 = simple_connect ( t, p, rst );
                r->numSegs = 2;
                r->seg = (segment*)calloc(2,sizeof(segment));
                r->seg[0] = s1;
                r->seg[1] = s2;
                ld_seg_net ( r->seg, net_id, rst );
                ld_seg_net ( r->seg+1, net_id, rst );
        }
}

float   bb_factor ( int vio )
{
        if ( vio <= 10 )
                return  0;
        if ( vio <= 100 )
                return  0.3;
        if ( vio <= 1000 )
                return  0.6;
        if ( vio <= 10000 )
                return  0.9;
        return  1.2;
}
void    Z_route ( route *r, int net_id, routingInst *rst )
{
        // only consider Z-shape
        int     s = r->s;
        int     t = r->t;
        r->state = 1;
        if ( is_flat ( s, t, rst ) )
        {
                r->numSegs = 1;
                r->seg = (segment*)malloc(sizeof(segment));
                r->seg[0] = simple_connect ( s,t,rst );
                ld_seg_net ( r->seg, net_id, rst );
        }
        else
        {
        int     gx = rst->gx;
        int     dist = INFTY;
        segment sz1, sz2, sz3;
        sz1.dist = 0;   sz2.dist = 0;   sz3.dist = 0;
        sz1.edges = NULL;
        sz2.edges = NULL;
        sz3.edges = NULL;
        if ( s%gx != t%gx ) for ( int k = min(s%gx,t%gx); k<=max(s%gx,t%gx); k++ )
                {
                        int     s1 = gx*(s/gx)+k; 
                        int     t1 = gx*(t/gx)+k;
                        segment seg1 = simple_connect (s,s1,rst );
                        segment seg2 = simple_connect (s1,t1,rst );
                        segment seg3 = simple_connect (t1,t,rst );
                        if ( est_segment(&seg1,net_id,rst)+est_segment(&seg2,net_id,rst)+est_segment(&seg3,net_id,rst)<dist )
                        {
                                dist = est_segment(&seg1,net_id,rst)+est_segment(&seg2,net_id,rst)+est_segment(&seg3,net_id,rst);
                                sz1 = seg1;     sz2 = seg2;     sz3 = seg3;
                        }
                }
        if ( s/gx != t/gx )
                for ( int k = min(s/gx,t/gx); k<=max(s/gx,t/gx); k++ )
                {
                        int     s1 = gx*k+(s%gx); 
                        int     t1 = gx*k+(t%gx);
                        segment seg1 = simple_connect (s,s1,rst );
                        segment seg2 = simple_connect (s1,t1,rst );
                        segment seg3 = simple_connect (t1,t,rst );
                        if ( est_segment(&seg1,net_id,rst)+est_segment(&seg2,net_id,rst)+est_segment(&seg3,net_id,rst)<dist )
                        {
                                dist = est_segment(&seg1,net_id,rst)+est_segment(&seg2,net_id,rst)+est_segment(&seg3,net_id,rst);
                                sz1 = seg1;     sz2 = seg2;     sz3 = seg3;
                        }
                }
        r->numSegs = 3;
        r->seg = (segment*)calloc(3,sizeof(segment));
        r->seg[0] = sz1;
        r->seg[1] = sz2;
        r->seg[2] = sz3;
        ld_seg_net ( r->seg, net_id, rst );
        ld_seg_net ( r->seg+1, net_id, rst );
        ld_seg_net ( r->seg+2, net_id, rst );
        }
}

void    simple_net ( int net_id, routingInst *rst )
{
        net     *n = rst->nets+net_id;
        int     numPins = n->numPins;
        for ( int i = 0; i < numPins-1; i++ )
                Z_route ( n->r+i, net_id, rst );
        for ( int_LL *node = n->edges; node->next; node=node->next )
        {
                int     id = node->next->num;
                ++ rst->edgeUtils[id];
                rst->edgeWeights[id] = dfn_weight( rst->edgeUtils[id], rst->edgeCaps[id], rst->hist[id] );
        }
}
int_LL  *neighbor ( int id, routingInst *rst, int xmin, int ymin, int xmax, int ymax )
{
        int_LL  *neighbor = new_int_LL();
        int     gx = rst->gx;
        int     x = id % gx;
        int     y = id / gx;
        if ( x > xmin )          // left neighbor
                insert_int_LL ( y * gx + x-1, neighbor );
        if ( x < xmax )       // right neighbor
                insert_int_LL ( y * gx + x+1, neighbor );
        if ( y > ymin )          // down neighbor
                insert_int_LL ( (y-1)*gx + x, neighbor );
        if ( y < ymax )       // up neighbor
                insert_int_LL ( (y+1)*gx + x, neighbor );
        return  neighbor;
}
float   weight_between ( int p1, int p2, routingInst *rst )
{
        point   pt1 = id_to_pt ( p1, rst );
        point   pt2 = id_to_pt ( p2, rst );
        int     edge_id = find_edge_id ( pt1.x, pt1.y, pt2.x, pt2.y, rst );
        return  rst->edgeWeights[edge_id];
}
void    reconstruct_path ( int  *came_from, int start, int goal, int net_id, route *r, routingInst *rst )
{
        int     cur = goal;
        int_LL  *pins = new_int_LL ();
        insert_int_LL ( cur, pins );
        while ( came_from[cur] != start )
        {
                int     flat = is_in_line (came_from[came_from[cur]], came_from[cur], cur, rst ); 
                if ( !flat )
                        insert_int_LL ( came_from[cur], pins );
                cur = came_from[cur];
        }
        insert_int_LL ( start, pins );

        int     *val = int_LL_to_array ( pins );
        r->numSegs = length_int_LL ( pins ) - 1;
        segment *seg = (segment*)calloc(r->numSegs, sizeof(segment));
        for ( int i = 0; i < r->numSegs; i++ )
        {
                seg[i] = simple_connect ( val[i], val[i+1], rst );
                ld_seg_net ( seg+i, net_id, rst );
        }
        r->seg = seg;
}

void    A_star_route ( route *r, int net_id, routingInst *rst, int width )
{
        int     start =r->s;
        int     goal = r->t;
        r->state = 1;

        int     num = rst->gx*rst->gy;
        int     xmin = min ( start % rst->gx, goal % rst->gx );
        int     xmax = max ( start % rst->gx, goal % rst->gx );
        int     ymin = min ( start / rst->gx, goal / rst->gx );
        int     ymax = max ( start / rst->gx, goal / rst->gx );

        xmin = max ( 0, xmin-width );
        xmax = min ( rst->gx-1, xmax+width );
        ymin = max ( 0, ymin-width );
        ymax = min ( rst->gy-1, ymax+width );

        int     *openset = new_array ( num );
        openset[0] = 1;
        openset[1] = start;
        int_LL  *closedset = new_int_LL ();
        float   *f = new_float_array ( num );
        float   *g = new_float_array ( num );
        int     *p = new_array ( num );

        g[start] = 0;
        f[start] = g[start] + pt_dist ( start, goal, rst );
        while   (openset[0])
        {
                int     cur = pull_priority_queue ( openset, f );
                if ( cur == goal )
                {
                        reconstruct_path ( p, start, goal, net_id, r, rst );
                        free (f);
                        free (g);
                        free (p);
                        free (openset);
                        free (closedset);
                        return;
                }
                insert_int_LL ( cur, closedset );
                for ( int_LL *node = neighbor ( cur, rst , xmin, ymin, xmax, ymax ); node->next; node=node->next )
                {
                        int     adj = node->next->num;
                        float   tmp_g = g[cur] + weight_between ( cur, adj, rst );
                        if ( find_int_LL ( adj, closedset ) && ( g[adj] <= tmp_g) )
                                continue;
                        if ( !is_in_queue ( adj, openset ) || (g[adj] > tmp_g) )
                        {
                                p[adj] = cur;
                                g[adj] = tmp_g;
                                f[adj] = g[adj] + pt_dist ( adj, goal, rst );
                                if ( !is_in_queue ( adj, openset ) )
                                        insert_priority_queue ( adj, openset, f );
                        }
                }
        }
        return;
}

void    smart_net_route ( int net_id, routingInst *rst )
{
        net     *n = rst->nets+net_id;
        int     numPins = n->numPins;
        n->edges = new_int_LL ();

        for ( int i = 0; i < numPins-1; i++ )
                Z_route ( n->r+i, net_id, rst );
        for ( int_LL *node = n->edges; node->next; node=node->next )
        {
                int     id = node->next->num;
                ++ rst->edgeUtils[id];
                rst->edgeWeights[id] = dfn_weight( rst->edgeUtils[id], rst->edgeCaps[id], rst->hist[id] );
        }
}
void    A_star_net_route ( int net_id, routingInst *rst, int width )
{ 
        net     *n = rst->nets+net_id;
        int     numPins = n->numPins;
        n->edges = new_int_LL ();

        for ( int i = 0; i < numPins-1; i++ )
                A_star_route ( n->r+i, net_id, rst, width );
        for ( int_LL *node = n->edges; node->next; node=node->next )
        {
                int     id = node->next->num;
                ++ rst->edgeUtils[id];
                rst->edgeWeights[id] = dfn_weight( rst->edgeUtils[id], rst->edgeCaps[id], rst->hist[id] );
        }
}
int     pins_within_bb ( int net_id, routingInst *rst )
{
        net     *n = rst->nets + net_id;
        int     xmax = 0, xmin = rst->gx;
        int     ymax = 0, ymin = rst->gy;
        for ( int i = 0; i < n->numPins; i++ )
        {
                int     x = n->pins[i] % rst->gx;
                int     y = n->pins[i] / rst->gx;
                xmin = min ( xmin, x );
                xmax = max ( xmax, x );
                ymin = min ( ymin, y );
                ymax = max ( ymax, y );
        }
        int     c = 0;
        for ( int i = xmin; i<=xmax; i++ )
                for ( int j = ymin; j <= ymax; j++ )
                        if ( rst->nodeUtils[j*rst->gx+i])
                                ++ c;
        return  c;
}
int     *net_ordering ( routingInst *rst )
{
        float   *pins_within = new_float_array ( rst->numNets );
        assign_float_array ( pins_within, rst->numNets, 0 );
        for ( int i = 0; i<rst->numNets; i++ )
                pins_within[i] = (float)pins_within_bb ( i, rst );
        int     *net_order = sort_array ( pins_within, rst->numNets ); 
        return  net_order;
}
